/*----------------------------------------------------------------------------
 * Copyright (c) <2013-2017>, <Huawei Technologies Co., Ltd>
 * All rights reserved.
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 * 1. Redistributions of source code must retain the above copyright notice, this list of
 * conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
 * of conditions and the following disclaimer in the documentation and/or other materials
 * provided with the distribution.
 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
 * to endorse or promote products derived from this software without specific prior written
 * permission.
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *---------------------------------------------------------------------------*/
/*----------------------------------------------------------------------------
 * Notice of Export Control Law
 * ===============================================
 * Huawei LiteOS may be subject to applicable export control laws and regulations, which might
 * include those applicable to Huawei LiteOS of U.S. and the country in which you are located.
 * Import, export and usage of Huawei LiteOS in any manner by you shall be in compliance with such
 * applicable export control laws and regulations.
 *---------------------------------------------------------------------------*/

/* Architecture Analysis
 *********************************************************************************************
 *      The USB Devices Topology    ---    Translate   -->  Binary Tree Map
 *               BUS                                             BUS
 *                |                                              /
 *       ---------------------                                  /
 *       |                   |                                 H01
 *      H01                 H02...                             / \
 *       |                   |                                /   \
 * ------------      ---------------                        H11    \---------H02
 * |          |      |             |         ------\        / \              / \
 *H11        H12... H21           H22...     -------\      /   \            /   \
 * |          |      |             |         -------/     D1   H12         H21  ...
 *D1         D2      |            D3         ------/           / \         / \
 *              ------------                                  /   \       /   \
 *              |          |                                 D2   ...    H31   \----H22
 *             H31        H32...                                          / \        / \
 *              |          |                                             /   \      /   \
 *             D4         D5                                            D4   H32   D3   ...
 *                                                                      / \
 *                                                                     /   \
 *                                                                    D5   ...
 *********************************************************************************************
 */

#include "implementation/usb_btree.h"
#include "los_printf_pri.h"
#include <stdlib.h>
#include <string.h>

//#define USB_BINARY_TREE_DEBUG
#ifdef USB_BINARY_TREE_DEBUG
#define bt_debug(x...) dprintf(x)
#else
#define bt_debug(x...) do{}while(0)
#endif

extern usbd_btTree hub_tree;

struct usbd_btNode *usbd_create_btNode(struct node_info *info)
{
    struct usbd_btNode *node = (usbd_btNode *)malloc(sizeof(usbd_btNode));
    if (node == NULL) {
        PRINT_ERR("Binary tree node alloc failed!\n");
        return NULL;
    }

    (void)memset_s(&node->info, sizeof(node->info), 0, sizeof(node->info));
    node->info.port_no = info->port_no;
    node->info.nameunit = info->nameunit;
    node->lbtNode = NULL;
    node->rbtNode = NULL;

    bt_debug("[create node] %p %s %d\n", node, node->info.nameunit, node->info.port_no);
    return node;
}

void usbd_free_btNode(usbd_btNode *node)
{
    bt_debug("[free node] %p %s %d\n", node, node->info.nameunit, node->info.port_no);

    node->info.nameunit = NULL;
    node->info.port_no = 0;
    node->lbtNode = NULL;
    node->rbtNode = NULL;

    free(node);
}

static void usbd_release_btNode(usbd_btNode *node)
{
    if (node == NULL)
        return;

    usbd_release_btNode(node->lbtNode);
    usbd_release_btNode(node->rbtNode);

    if (node->info.nameunit != NULL)
        usbd_free_btNode(node);
}

static struct usbd_btNode *usbd_preOrder_btNode(usbd_btNode *node, struct node_info *info)
{
    usbd_btNode *lNode = NULL, *rNode = NULL;

    if (node == NULL) {
        return NULL;
    }

    if (node->info.nameunit == info->nameunit) {
        if (node->info.port_no == info->port_no) {
            return node;
        }
    }

    lNode = usbd_preOrder_btNode(node->lbtNode, info);
    if (lNode != NULL) {
        return lNode;
    }
    rNode = usbd_preOrder_btNode(node->rbtNode, info);
    if (rNode != NULL) {
        return rNode;
    }

    return NULL;
}

static bool f_find_device = 0;
static struct usbd_btNode *usbd_preOrder_hubNode(usbd_btNode *node, char *devname, uint8_t *port_num)
{
    usbd_btNode *lNode = NULL, *rNode = NULL;

    if (node == NULL) {
        return NULL;
    }

    if (!strncmp(node->info.nameunit, "uhub", strlen("uhub"))) {
        bt_debug("[Hub Node] %p %s %d %d\n", node, node->info.nameunit, node->info.port_no, *port_num);
        if (node->lbtNode == NULL) {
            (*port_num)--;
        } else {
            if (!strncmp(node->lbtNode->info.nameunit, devname, strlen(devname))) {
                (*port_num)--;
                if (*port_num == 0)
                    f_find_device = 1;
            }
        }
        if (*port_num == 0) {
            return node->lbtNode;
        }
    }

    lNode = usbd_preOrder_hubNode(node->lbtNode, devname, port_num);
    if (lNode != NULL) {
        return lNode;
    }
    rNode = usbd_preOrder_hubNode(node->rbtNode, devname, port_num);
    if (rNode != NULL) {
        return rNode;
    }
    return NULL;
}

static void usbd_perOrder_hub_quantity(usbd_btNode *node, uint8_t *port_qty)
{
    if (node == NULL) {
        return;
    }

    if (!strncmp(node->info.nameunit, "uhub", strlen("uhub"))) {
        if (node->lbtNode == NULL) {
            (*port_qty)++;
        } else {
            if (strncmp(node->lbtNode->info.nameunit, "uhub", strlen("uhub"))) {
                (*port_qty)++;
            }
        }
    }

    usbd_perOrder_hub_quantity(node->lbtNode, port_qty);
    usbd_perOrder_hub_quantity(node->rbtNode, port_qty);
}

int usbd_get_hub_quantity(void)
{
    uint8_t quantity = 0;

    usbd_perOrder_hub_quantity(hub_tree, &quantity);

    return quantity;
}

struct usbd_btNode *usbd_perOrder_probe(usbd_btTree tree, char *devname, uint8_t *port_num)
{
    usbd_btNode *node = usbd_preOrder_hubNode(tree, devname, port_num);

    if ((node != NULL) && f_find_device) {
        f_find_device = 0;
        return node;
    }

    return NULL;
}

int usbd_insert_btNode(usbd_btNode *node, usbd_btTree tree, struct node_info *parent_info)
{
    usbd_btNode *parent_node = NULL;

    if (node == NULL || tree == NULL || parent_info == NULL)
        return -1;

    parent_node = usbd_preOrder_btNode(tree, parent_info);
    if (parent_node == NULL) {
        PRINT_ERR("Find err, insert fail!\n");
        return -1;
    }

    if (parent_node->info.nameunit == node->info.nameunit) {  /* The same hub node. */
        parent_node->rbtNode = node;
    } else {  /* Other driver(hub or other) */
        parent_node->lbtNode = node;
    }

    bt_debug("[insert node] parent:%p %s %d\n \
             %s child :%p %s %d\n", \
                    parent_node, parent_node->info.nameunit, parent_node->info.port_no, \
                    (parent_node->info.nameunit == node->info.nameunit ? "right" : "left"), \
                    node, node->info.nameunit, node->info.port_no);
    return 0;
}

int usbd_remove_btNode(usbd_btTree tree, struct node_info *p_info, struct node_info *rm_info)
{
    usbd_btNode *rm_node = NULL;

    if (tree == NULL || p_info == NULL || rm_info == NULL)
        return -1;

    rm_node = usbd_preOrder_btNode(tree, rm_info);
    if (rm_node == NULL) {
        bt_debug("Find err, remove fail!\n");
        return -1;
    }

    usbd_release_btNode(rm_node);

    /* release parent left node */
    rm_node = usbd_preOrder_btNode(tree, p_info);
    if (rm_node == NULL) {
        PRINT_ERR("Parent find err, remove fail!\n");
        return -1;
    }
    rm_node->lbtNode = NULL;

    return 0;
}

